import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * Klasa uzywana jest do wywolania Algorytmu Wspinaczki na instancji problemu
 * podzialu zbioru.
 * 
 * @author Ewa Byra (nr indeksu s6405)
 */
public class MultiHillClimbingAlgorithm {
	private List<Partition> problemSolutions;

	/**
	 * Konstruktor klasy. Generowanie sa w nim wszystkie mozliwe rozwiazania
	 * problemu.
	 * 
	 * @param data
	 *            Instancja problemu podzialu zbioru.
	 */
	public MultiHillClimbingAlgorithm(List<Integer> data) {
		this.problemSolutions = Generator
				.generateDataToHillClimbingAlgorithm(data);
	}

	/**
	 * Glowna metoda sluzaca do wytypowania rozwiazania z jak najmniejsza
	 * wartoscia funkcji oceny. Opiera sie na algorytmie wspinaczki
	 * wielosciezkowej. Glowna petla algorytmu ma nastepujacy przebieg:<br>
	 * 1. Wyznaczanie "najlepszego sasiada" sposrod wszystkich aktualnie
	 * odwiedzanych punktow<br>
	 * 2. Porownianie wyniku funkcji przystosowania "najlepszego sasiada" z
	 * funkcja przystosowania kazdego z aktualnie odwiedzanych punktow. Na
	 * podstawie powyzszego porownania wytypowana zostaje nastepny punkt dla
	 * danej sciezki<br>
	 * 3. Sprawdzenie warunku zatrzymania petli - w chwili, gdy wszytskie
	 * sciezki sie polaczyly, a wsrod sasiadow nie ma lepszego rozwiazania<br>
	 * 
	 * @param beam
	 *            Liczba rownolegle analizowanych sciezek.
	 * @return Przyblizone rozwiazanie problemu.
	 */
	public Partition runAlgorithm(int beam) {
		List<Integer> startIndexes = new ArrayList<>();
		List<Partition> neighbors = new ArrayList<>();
		List<Partition> currentlyVisited = new ArrayList<>();
		Partition theBestNeighbor;
		Random generator = new Random();
		int index;
		boolean condition = true;

		/* Losowanie punktow startowych sciezek */
		while (startIndexes.size() != beam) {
			index = generator.nextInt(problemSolutions.size());
			if (!startIndexes.contains(index))
				startIndexes.add(index);
		}

		/*
		 * Wytypowanie wszystkich rozwazanych sasiadow i inicjalizacja listy
		 * sciezek
		 */
		for (int i = 0; i < startIndexes.size(); i++) {
			neighbors.addAll(problemSolutions.get(startIndexes.get(i))
					.getNeighbors());
			currentlyVisited.add(problemSolutions.get(startIndexes.get(i)));
		}

		/* Wyznaczenie najlepszego sasiada */
		theBestNeighbor = neighbors.get(0);
		for (int i = 1; i < neighbors.size(); i++) {
			if (neighbors.get(i).getFit() < theBestNeighbor.getFit()) {
				theBestNeighbor = neighbors.get(i);
			}
		}

		while (condition) {

			/* Wyznaczenie dalszych drog */
			for (int i = 0; i < currentlyVisited.size(); i++) {
				if (currentlyVisited.get(i).getFit() > theBestNeighbor.getFit()) {
					currentlyVisited.set(i, theBestNeighbor);
				}
			}

			/* Nowa lista sasiadow */
			neighbors = new ArrayList<>();
			for (int i = 0; i < currentlyVisited.size(); i++) {
				neighbors.addAll(currentlyVisited.get(i).getNeighbors());
			}

			/* Nowy najlepszey sasiad */
			theBestNeighbor = neighbors.get(0);
			for (int i = 1; i < neighbors.size(); i++) {
				if (neighbors.get(i).getFit() < theBestNeighbor.getFit()) {
					theBestNeighbor = neighbors.get(i);
				}
			}

			/* Sprawdzanie czy wszystkie sciezki sie zbiegly */
			for (int i = 0; i < currentlyVisited.size() - 1; i++) {				
				if (!currentlyVisited.get(i)
						.equals(currentlyVisited.get(i + 1))) {
					condition = false;
					break;
				}
			}
			/*
			 * Sprawdzanie czy dalsza droga nie da lepszego rozwiazania i
			 * ewentualne zatrzymanie petli
			 */
			if (condition
					&& theBestNeighbor.getFit() > currentlyVisited.get(0)
							.getFit())
				break;
		}

		return currentlyVisited.get(0);
	}

}
